package com.zhugang.week05;

import java.util.HashSet;
import java.util.Set;

/**
 * @program algorithms
 * @description: findSwapValues
 * @author: chanzhugang
 * @create: 2022/07/11 16:28
 */
public class FindSwapValues {

    public static void main(String[] args) {
        FindSwapValues findSwapValues = new FindSwapValues();
        int[] array1 = new int[]{4, 1, 2, 1, 1, 2};
        int[] array2 = new int[]{3, 6, 3, 3};
        int[] res = findSwapValues.findSwapValues(array1, array2);
        for (int num : res) {
            System.out.println(num);
        }
    }

    /**
     * 面试题 16.21 交换和
     *
     * @param array1
     * @param array2
     * @return
     */
    public int[] findSwapValues(int[] array1, int[] array2) {
        // 交换一对数值，使两个数组所有元素和相等，返回交换的值
        // sum1 + sum2 如果为奇数，无解； arr2元素放哈希表，遍历arr1，如果元素 + 差值在哈希表中，则存在解
        int sum1 = 0;
        for (int i = 0; i < array1.length; i++) {
            sum1 += array1[i];
        }
        int sum2 = 0;
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < array2.length; i++) {
            int num = array2[i];
            set.add(num);
            sum2 += num;
        }
        // 肯定无解
        int sum = sum1 + sum2;
        if (sum % 2 == 1) {
            return new int[0];
        }
        // 差值
        int diff = sum / 2 - sum1;
        for (int i = 0; i < array1.length; i++) {
            // 另一个数组交换的值
            int target = array1[i] + diff;
            if (set.contains(target)) {
                return new int[]{array1[i], target};
            }
        }
        return new int[]{};
    }
}